/**
 * Copyright (Warren)
 * FileName: _3_LongestSubstringWithoutRepeatingCharacters
 * Author:
 * Date:     2019/3/10 1:20
 * Description:
 * History:
 */
package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _3_LongestSubstringWithoutRepeatingCharacters {
    class Solution {
        //
        public int lengthOfLongestSubstring1(String s) {
            int[] freq = new int[256];
            int res = 0;
            int curLen = 0;
            Arrays.fill(freq, -1);
            for (int i = 0; i < s.length(); i++) {
//                if (freq[s.charAt(i)] == -1 || (i - freq[s.charAt(i)]) > curLen) {
                if (freq[s.charAt(i)] == -1 ) {
                    curLen++;
                    freq[s.charAt(i)] = i;
                    if (res < curLen) res = curLen;
                } else {
                    curLen = i - freq[s.charAt(i)];
                    freq[s.charAt(i)] = i;
                }
            }
            return res;
        }


        /*
                public int lengthOfLongestSubstring(String s) {
                    char[] strArr = s.toCharArray();
                    ArrayList<Character> curr =  new ArrayList<Character>();
                    int record = 0;
                    int temp = 0;
                    int pos = 1;
                    for (int i = 0; i < strArr.length; i++){
                        char c = strArr[i];
                        if (curr.contains(c)) {
                            curr.clear();
                            if (temp > record) {
                                record = temp;
                            }
                            temp = 0;
                            i = pos;
                            pos++;
                        }else {
                            curr.add(c);
                            temp++;
                            if(record < temp) record = temp;
                            if (strArr.length-i == 1) record++;
                        }
                    }
                    return record;
                }
            }
        */
        public int lengthOfLongestSubstring(String s) {
            int[] freq = new int[256];
            int maxLen = 0;
            int curLen = 0;
            int i = 0;

            Arrays.fill(freq, -1); //使用-1填充freq数组

            for (i = 0; i < s.length(); i++) {
                if (freq[s.charAt(i)] == -1) {
                    curLen = curLen + 1;
                    freq[s.charAt(i)] = i;
                    if (curLen > maxLen) {
                        maxLen = curLen;
                    }
                } else {
                    if (i - freq[s.charAt(i)] > curLen) {
                        curLen++;
                        freq[s.charAt(i)] = i;
                        if (curLen > maxLen) {
                            maxLen = curLen;
                        }
                    } else {
                        curLen = i - freq[s.charAt(i)];
                        freq[s.charAt(i)] = i;
                    }
                }
            }
            return maxLen;
        }
    }

    public Solution getSolution() {
        return new Solution();
    }

    public static void main(String[] args) {
        _3_LongestSubstringWithoutRepeatingCharacters c = new _3_LongestSubstringWithoutRepeatingCharacters();
        _3_LongestSubstringWithoutRepeatingCharacters.Solution s = c.getSolution();
        String s1 = "tmmzuxt";
        int result = s.lengthOfLongestSubstring1(s1);
        System.out.print(result);
    }
}

